Min Cut

定义 Definition

min cut（最小割）：在图论中，指把一个网络/图分成两个部分（通常包含源点 s 和汇点 t 分别在不同部分）所需要“切断”的边的最小总容量/最小代价。常与 max flow（最大流）一起出现（最大流最小割定理）。在更广义语境中也可指“最小切割”这一类优化问题。

发音 Pronunciation (IPA)

/ˌmɪn ˈkʌt/

例句 Examples

The algorithm computes the min cut in the network.
该算法会计算网络中的最小割。

By the max-flow min-cut theorem, the value of the maximum flow equals the capacity of the min cut.
根据最大流最小割定理，最大流的值等于最小割的容量。

词源 Etymology

min 是 minimum（最小值）的缩写；cut 在图论里指把图“割开/切分”的操作或结果。合起来 min cut 就是“最小的切割（代价）”，用来描述在网络流问题中代价最小的分割方式。

相关词 Related Words

• Algorithm
• Capacity
• Edge
• Flow
• Graph
• Max Flow
• Partition
• Theorem
• Vertex

文学与著作中的用例 Literary / Notable Works

• Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein，常称 CLRS）：在“最大流”章节系统讲解 min cut 与相关定理。
• Network Flows: Theory, Algorithms, and Applications（Ahuja, Magnanti, Orlin）：以网络流为核心，频繁使用 minimum cut / min cut。
• Ford, L. R. & Fulkerson, D. R. 的经典网络流研究论文与专著（20 世纪中期）：奠定最大流/最小割理论框架，讨论 min cut 概念与算法。